This invention relates to encoders and, more particularly, to multiple description encoders.
FIG. 1 depicts encoders 10, 11, 12 that are responsive to an input signal, developing code signal streams S1, S2, and S3, respectively. Illustratively, encoders 10, 11 and 12 output 3 bit codes and are, in a sense, the same except for an offset. For example, encoder 10 outputs index 0 for signals, A, in the range 0≦s<u, (where u is ⅛ of the signal's dynamic range M; i.e.,
      u    =          M      8        )and outputs index 1 in the range u≦s<2u, etc.; encoder 11 is offset by u/3, so it outputs index 0 in the range
      u    3    ≤  s  <            4      ⁢                          ⁢      u        3  and outputs index 1 in the range
                    4        ⁢                                  ⁢        u            3        ≤    s    <                  7        ⁢                                  ⁢        u            3        ,etc., and encoder 12 outputs is offset by
            2      ⁢                          ⁢      u        3    ,so it outputs index 0 in the range
            2      ⁢                          ⁢      u        3    ≤  s  <            5      ⁢                          ⁢      u        3  and outputs index 1 in the range
                    5        ⁢                                  ⁢        u            3        ≤    s    <                  8        ⁢                                  ⁢        u            3        ,etc. This is shown in FIG. 2A. In this arrangement, signal s can be decoded with granularity of
  u  3when all three of the code streams S1, S2, and S3 are available for decoding. When only one of the code streams is available, the signal can still be coded, albeit, with granularity of only u, and when two of the steams are available, in some signal ranges the granularity is u, and in other signal ranges the granularity is
      u    3    .On average, the granularity is
      u    2    .
The FIG. 1 arrangement can also be structured as a multiple description encoding arrangement that provides precisely the granularity
  u  2by, for example, arranging encoder 12 to produce an output that is the Exclusive OR of encoders 10 and 11. This is shown in FIG. 2B. The encoded signal, A, can be recovered with granularity
  u  2from signals S1 and S2. If one of those signals is not available but signal S3 is available, the encoded signal can still be recovered because the missing signal can be reconstituted from signal S3. In other words, the three-encoder arrangement where encoder 12 outputs the Exclusive Or of encoder 10 and 11 includes redundancy, and this redundancy permits recovery of the signal when one of the three code streams is missing.
FIG. 3 depicts a prior art encoder that transmits at a rate that is the same as that of the FIG. 1 encoder, but sends less information. This is accomplished by binning function elements 20, 21, and 22 that are connected at the outputs of encoders 13, 14, and 15, respectively. Each quantizer-binning element pair (such as quantizer 12 and binning element 23) can be viewed as a sub-encoder of the FIG. 3 encoder.
A binning function is a many-to-one mapping function and, consequently, the amount of information at the output is less than the amount of information at the input. Without more, this loss of information is not recoverable. One example of a binning function is a modulus truncation, where incoming codes are expressed in terms of their equivalents, modulo a preselected base, m, where m<M and M is the dynamic range of incoming codes. Each of the codes that a binning element is capable of producing can be viewed as a bin into which incoming codes are dropped (hence the term “binning”).
It can be shown that the FIG. 3 embodiment that provides redundancy (such as where the third description is the Ex-Or of the other two descriptions), the incoming signal A can be recovered from descriptions D1, D2, and D3, even though, as indicated above, the binning information loses information. Proof of this capability is provided, for example, in “N-channel symmetric multiple descriptions—Part I: (n, k) source-channel erasure codes,” Pradhan et al, IEEE Trans. Information Theory, vol. 50, pp. 47-61, January 2004. See, also “Source-Channel Erasure Codes with Lattice Codebooks for Multiple Description Coding,” 2006 IEEE International Symposium on Information Theory, where Ostergaard, J. et al have shown that a subset of the rate distortion region of the symmetric N-channel multiple description coding problem can be achieved by use of (N:K) source-channel erasure codes (SCEC). That is, what the prior art has shown is that an encoder can be designed to produce N multiple descriptions that employ binning where decoding can be carried out if K or more of the multiple description are available, where K<N. Herein, such an encoder is termed an (N:K) multiple description binning encoder.
No arrangements are known that permit use of binning and also recovering of the input signal with fewer than K of the descriptions.